package com.yoshino.leetcode.improve40.twentysixth;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public int findKthLargest2(int[] nums, int k) {
        // 优先队列
        PriorityQueue<Integer> queue = new PriorityQueue<>(k);
        for (int num : nums) {
            queue.offer(num);
            if (k < queue.size()) {
                queue.poll();
            }
        }
//        Arrays.sort(nums);
//        return nums[nums.length - k];
        return queue.peek();
    }

    public int findKthLargest(int[] nums, int k) {
        // 优先队列
        PriorityQueue<Integer> queue = new PriorityQueue<>(k);
        for (int i = 0; i < k; i++) {
            queue.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (queue.peek() < nums[i]) {
                queue.poll();
                queue.offer(nums[i]);
            }
        }
        return queue.peek();
    }

    // 归并排序
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 得到后半段结点的头结点
        ListNode listNode = spiltNode(head);
        head = sortList(head);
        listNode = sortList(listNode);
        return merge(head, listNode);
    }

    private ListNode merge(ListNode head, ListNode listNode) {
        // 上述两个 队列 都是分别有序的
        ListNode root = new ListNode(-1);
        ListNode cur = root;
        while (head != null && listNode != null) {
            if (head.val < listNode.val) {
                cur.next = head;
                head = head.next;
            } else {
                cur.next = listNode;
                listNode = listNode.next;
            }
            cur = cur.next;
        }
        if (head != null) {
            cur.next = head;
        }
        if (listNode != null) {
            cur.next = listNode;
        }
        return root.next;
    }

    private ListNode spiltNode(ListNode head) {
        // 预防只有 两结点的情况，出现 后段结点只出现 null情况
        ListNode virtual = new ListNode(-1, head);
        ListNode slow = virtual, fast = virtual;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode res = slow.next;
        // 截断
        slow.next = null;
        return res;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        // 优先队列
        if (lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for (int i = 0; i < lists.length; i++) {
            ListNode cur = lists[i];
            while (cur != null) {
                queue.offer(cur);
                cur = cur.next;
            }
        }
        ListNode head = queue.poll();
        ListNode cur = head;
        while (!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
        }
        if (cur.next != null) {
            cur.next = null;
        }
        return head;
    }
}

